package com.leetcode;

import java.util.Scanner;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No204
 * @description 204 计数质数
 * @date 2021/1/29 上午11:54
 */
public class No204 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = countPrimes(n);
        System.out.println(res);

    }

    public static int countPrimes(int n) {
        if(n <= 1){
            return 0;
        }
        boolean[] isPrime = new boolean[n + 1];
        int primeCount = 0;
        int edge = (int)Math.sqrt(n) + 1;
        for (int i = 2; i < n ; i++) {
            if(isPrime[i]){
                continue;
            }
            primeCount++;
            // 标识前面的都是合数
            if(i <= edge){
                for (int j = i * i; j < n ; j += i) {
                    isPrime[j] = true;
                }
            }

        }
        return primeCount;
    }

}
